﻿using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Windows.Forms;

using System.IO;
using System.Text.RegularExpressions;
using System.Diagnostics;

namespace wordgamedictionary
{
    public partial class FormMain : Form
    {
        Dictionary dict;

        public FormMain()
        {
            InitializeComponent();

            buttonLoadDictionary.Click += buttonLoadDictionary_Click;
            buttonSearch.Click += buttonSearch_Click;

            dict = new Dictionary();
        }

        void UnloadDictionary()
        {
            dict.Clear();
        }

        void LoadDictionary(string data)
        {
            dict.Load(data);
        }

        void buttonLoadDictionary_Click(object sender, EventArgs e)
        {
            DialogResult result = openFileDictionary.ShowDialog();
            if (result == DialogResult.OK) // Test result.
            {
                UnloadDictionary();

                string file = openFileDictionary.FileName;
                try
                {
                    LoadDictionary(File.ReadAllText(file));
                }
                catch (IOException)
                {
                }
            }
        }

        void buttonSearch_Click(object sender, EventArgs e)
        {
            textBoxOutput.Clear();

            string matches = dict.MatchCharacters(textBoxLetters.Text, textBoxPattern.Text);

            textBoxOutput.AppendText(matches);
        }

        private void openFileDialog1_FileOk(object sender, CancelEventArgs e)
        {

        }
    }

    public class Dictionary
    {
        string[] words;
        uint[] searchKeys;
        uint[] searchKeyBits;

        public void Clear()
        {
            // this is c#, we don't really ever clear out the dictionary?
        }

        public uint CountBitsFaster32(uint number)
        {
	        // add bit sums
	        // 1s
	        number = (number & 0x55555555) + ((number & 0xaaaaaaaa) >> 1);
	        // 2s
	        number = (number & 0x33333333) + ((number & 0xcccccccc) >> 2);
	        // 4s
	        number = (number & 0x0f0f0f0f) + ((number & 0xf0f0f0f0) >> 4);

	        // at this point, every 8 bit field contains the number of bits in that 8 bit field
	        // it's time to use our modulo trick
	        number = number % 255;

	        return number;
        }


        public ulong CountBitsFaster64( ulong number )
        {
	        // add bit sums
	        // 1s
	        number = (number & 0x5555555555555555) + ((number & 0xaaaaaaaaaaaaaaaa) >> 1);
	        // 2s
	        number = (number & 0x3333333333333333) + ((number & 0xcccccccccccccccc) >> 2);
	        // 4s
	        number = (number & 0x0f0f0f0f0f0f0f0f) + ((number & 0xf0f0f0f0f0f0f0f0) >> 4);

	        // at this point, every 8 bit field contains the number of bits in that 8 bit field
	        // it's time to use our modulo trick
	        number = number % 255;

	        return number;
        }


        uint ComputeSearchKey(string word)
        {
            uint searchKey = 0;
            uint duplicates = 0;

            for (int i = 0; i < word.Length; ++i)
            {
                int nextCharBit = word[i] - 'A';
                uint charMask = (uint)(1 << nextCharBit);

                // see if this bit is already set;
                if ((searchKey & charMask) != 0)
                {
                    duplicates += 1;
                }
                else
                {
                    searchKey |= charMask;
                }
            }

            // set the top bits to be the duplicate count as far as possible
            // bits 26-31
            for (int j = 26; (duplicates > 0) && (j < 32); ++j)
            {
                searchKey |= (uint)(1 << j);
                duplicates --;
            }

            return searchKey;
        }

        public void Load(string data)
        {
            // first, uppercase it so we don't have weird case issues
            string dataUpper = data.ToUpper();

            // split on non word chars
            words = Regex.Split(dataUpper, @"\W+");

            Console.WriteLine("Loaded dictionary with {0} words in it", words.Count());

            int numWords = words.Count();

            // index the words for fast searching
            searchKeys = new uint[numWords];
            // precompute the number of bits in each key
            searchKeyBits = new uint[numWords];

            for (int i = 0; i < numWords; ++i)
            {
                string curWord = words[i];

                searchKeys[i] = ComputeSearchKey(curWord);
                searchKeyBits[i] = CountBitsFaster32(searchKeys[i]);

            }

        }

        bool IsCharSubSet(string word, string characters, int blankCount)
        {
            bool[] usedChars = new bool[characters.Length];

            for (int j = 0; j < characters.Length; ++j)
                usedChars[j] = false;

            for (int i = 0; i < word.Length; ++i)
            {
                bool foundChar = false;
                for (int j = 0; j < characters.Length; ++j)
                {
                    if (usedChars[j])
                        continue;

                    if (word[i] == characters[j])
                    {
                        usedChars[j] = true;
                        foundChar = true;
                        break;
                    }
                }

                if (!foundChar)
                {
                    if (blankCount == 0)
                        return false;

                    blankCount -= 1;
                }
            }
            return true;
        }

        public string MatchCharacters(string characters, string pattern)
        {
            if (words == null)
            {
                return "Dictionary not loaded!";
            }

            string charactersUpper = characters.ToUpper();
            int blankCount = 0;

            // count and remove blanks
            for (int i = 0; i < charactersUpper.Length; ++i)
            {
                if (charactersUpper[i] == '?')
                {
                    blankCount += 1;
                    charactersUpper = charactersUpper.Remove(i, 1);
                    --i;
                }
            }


            // use a StringBuilder with a large preallocation because string concats
            // will take forever reallocating memory.
            StringBuilder result = new StringBuilder(2 * 1024 * 1024);

            uint charactersKey = ComputeSearchKey(charactersUpper);

            int numWords = words.Count();
            uint numWordsFilteredFast = 0;
            uint numWordsAcceptedFast = 0;
            uint numWordsFilteredSlow = 0;
            uint numWordsAcceptedSlow = 0;

            // performance measurements
            Stopwatch stopwatch = new Stopwatch();
            stopwatch.Start();

            // scan over our whole dictionary
            for (int i = 0; i < numWords; ++i)
            {
                // fast out is to compare searchKeys.
                uint subset = searchKeys[i] & charactersKey;
                uint subsetBits = CountBitsFaster32(subset);

                if (searchKeyBits[i] > subsetBits + blankCount)
                {
                    numWordsFilteredFast++;
                    continue;
                }

                // fast accept if there are no duplicate characters
                if ((searchKeys[i] & 0xFC000000) != 0)
                {
                    if (IsCharSubSet(words[i], charactersUpper, blankCount))
                    {
                        result.AppendLine(words[i]);
                        numWordsAcceptedSlow++;
                    }
                    else
                        numWordsFilteredSlow++;

                }
                else
                {
                    result.AppendLine(words[i]);
                    numWordsAcceptedFast++;
                }
            }

            stopwatch.Stop();

            Console.WriteLine("words filtered out with searchKey = {0} ({1}%)", numWordsFilteredFast, 100.0f * numWordsFilteredFast / words.Length);
            Console.WriteLine("words accepted with fast accept = {0} ({1}%)", numWordsAcceptedFast, 100.0f * numWordsAcceptedFast / words.Length);
            Console.WriteLine("words filtered out with slow filter = {0} ({1}%)", numWordsFilteredSlow, 100.0f * numWordsFilteredSlow / words.Length);
            Console.WriteLine("words accepted with slow filter = {0} ({1}%)", numWordsAcceptedSlow, 100.0f * numWordsAcceptedSlow / words.Length);
            Console.WriteLine("time elapsed = {0} milliseconds", 1000.0f * stopwatch.ElapsedTicks / TimeSpan.TicksPerSecond);
            return result.ToString();
        }
    }
}
